<?php
/**
 * 题目链接 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/
 */

class Solution {

    /**
     * 两层for 轮询 会超时
     * @param int[] $prices
     * @return int
     */
    public static function maxProfit1(array $prices): int 
    {
        $len = count($prices);
        if ($len <= 1) {
            return 0;
        }
        $max = $prices[1] - $prices[0];

        for ($i=0; $i < $len - 1; $i++) { 
            for ($j=$i+1; $j < $len; $j++) { 
                if ($max < $prices[$j] - $prices[$i]) {
                    $max = $prices[$j] - $prices[$i];
                }
            }
        }

        return $max > 0 ? $max : 0;
    }

    /**
     * 用动态规划 维护当前最低价格 当前最大利润
     * @param int[] $prices
     * @return int
     */
    public static function maxProfit(array $prices): int 
    {
        $len = count($prices);
        if ($len <= 1) {
            return 0;
        }
        /** @var int 最大利润 */
        $max = 0;
        /** @var int 最低价格 */
        $minPrice = $prices[0];

        for ($i=0; $i < $len; $i++) { 
            $minPrice = min($minPrice, $prices[$i]);
            $max = max($max, $prices[$i] - $minPrice);
        }

        return $max > 0 ? $max : 0;
    }
}

$test = [
    [[7,1,5,3,6,4]],
    [[7,6,4,3,1]],
];
$result = [
    5,
    0,
];

foreach ($test as $key => $value) {
    $r = Solution::maxProfit($value[0]);
    if ($r !== $result[$key]) {
        echo sprintf("第%d个case不通过", $key) . PHP_EOL;
    }
    echo $r . PHP_EOL;
}